\section{向量到子空间的距离\textbullet 最小二乘法}

\begin{frame}{距离}
在解析几何中，两个点 $ \alpha$ 和 $ \beta$ 间的距离等于向量 $ \alpha- \beta$ 的长度。 在欧氏空间中我们同样可引入

\pause
\begin{definition}
  长度 $| \alpha- \beta|$ 称为向量 $ \alpha$ 和 $ \beta$ 的\emph{距离}， 记为 $d( \alpha,  \beta)$.
\end{definition}

\pause
\begin{observation*}[距离的三条基本性质]
\begin{enumerate}
      \item $d( \alpha,  \beta)=d( \beta,  \alpha)$;
\item $d( \alpha,  \beta) \geqslant 0$, 并且仅当 $ \alpha= \beta$ 时等号才成立;
    \item $d( \alpha,  \beta) \leqslant d( \alpha,  \gamma)+d( \gamma,  \beta)$ (三角形不等式).
        \end{enumerate}
      \end{observation*}
      \begin{proof}

\begin{enumerate}
\item 我们有
  \(
    d( \alpha,  \beta)=\norm{\alpha-\beta}=\norm{-1\cdot(\beta-\alpha)}=\norm{\beta-\alpha}=d( \beta,  \alpha).
  \)
\item 我们有
  \(
    d( \alpha,  \beta)=\norm{\alpha-\beta} \geqslant  0,
  \)
  且仅当 $ \alpha= \beta$ 时等号才成立。
\item 应用三角形不等式 (推论~\ref{113}) 有
\[
\begin{aligned}
d( \alpha,  \beta) &= \norm{\alpha-\beta}=\norm{(\alpha-\gamma)+(\gamma-\beta)} \\
& \leqslant \norm{\alpha-\gamma}+\norm{\gamma-\beta}\\
&= d( \alpha,  \gamma)+d( \gamma,  \beta).
\end{aligned}
\]
\end{enumerate}
\end{proof}


\end{frame}

\begin{frame}
  在中学所学几何中知道一个点到一个平面 (或一条直线) 上所有点的距离以垂线最短。
  下面可以证明一个固定向量和一个子空间中各向量间的距离也是以``垂线最短''。

  \begin{lemma}\label{143}
    \begin{wrapfigure}{r}{.4\textwidth}
  \centering
  \vspace{-1.5em}
  \begin{tikzpicture}[scale=.6]
    \shadedraw[->, thick, left color=green!10, right color=green!60, draw=green] (0,0) -- (4,0) -- (5,2) node[below left] {$W$} -- (1,2) -- cycle;
    \coordinate (A) at (1, .8);
    \coordinate (B) at (3.8, 1.2);
    \coordinate (C) at (3.8, 4);
    \draw[->, thick, magenta] (A) -- node[above,xshift=-1em] {$\beta-\delta$} (C);
    \draw[->, thick, magenta] (A) -- node[below] {$\gamma-\delta$} (B);
    \draw[->, thick, magenta] (B) -- node[right] {$\beta-\gamma$} (C);
    \pic [draw=magenta, angle radius=1.5mm] {right angle=A--B--C};
  \end{tikzpicture}
\end{wrapfigure}
  设$V$是欧氏空间，$\beta\in V$, $W$是$V$的子空间，$\gamma\in W$为$\beta$在$W$中的内射影。
那么 $\norm{\beta-\delta}$ （其中$\delta$在$W$变动） 恰好在$\delta=\gamma$处取得最小值，
      或者说，对任意$\delta\in W$ 有
      \[
        \norm{\beta-\delta}\geqslant \norm{\beta-\gamma};
      \]
      而且等号成立当且仅当$\delta=\gamma$.
  \end{lemma}
  \begin{proof}
    既然$\gamma\in W$为$\beta$在$W$中的内射影，我们有$\beta-\gamma\perp W$.
由勾股定理知
  \begin{align*}
    \norm{\beta-\delta}^2 &=  \norm{(\beta-\gamma)+(\gamma-\delta)}^2\\
    &=  \norm{\beta-\gamma}^2 + \norm{\gamma-\delta}^2\\
    & \geqslant \norm{\beta-\gamma}^2.
  \end{align*}
  因此$\norm{\beta-\delta}\geqslant \norm{\beta-\gamma}$, 而且显然等号成立当且仅当
  $\norm{\gamma-\delta}^2=0$, 即$\delta=\gamma$.
  \end{proof}
\end{frame}
\iffalse
\begin{frame}
\begin{lemma}
  设$V$是欧氏空间，$\beta\in V$, $W$是$V$的子空间，$\gamma\in W$. 下列条件等价：
  \begin{enumerate}
    \item $\gamma$为$\beta$在$W$中的内射影（即$\beta=\gamma+\beta'$, 其中$\gamma\in W, \beta'\in W^\perp$）；
      \pause
    \item $\gamma$满足$\beta-\gamma\perp W$;
      \pause
    \item $\norm{\beta-\delta}$ （其中$\delta$在$W$变动） 在$\delta=\gamma$处取得最小值，即
      \[
        \min_{\delta\in W}\norm{\beta-\delta}=\norm{\beta-\gamma}.
      \]
      或者说，$\norm{\beta-\delta}\geqslant \norm{\beta-\gamma}$, 对任意$\delta\in W$.
    \end{enumerate}
\end{lemma}

  \begin{proof}(1)$\Rightarrow$(2) 是显然的，我们来证明 (2)$\Rightarrow$(3)$\Rightarrow$(1). 

    \pause
  (2)$\Rightarrow$(3) 假设$\gamma\in W$满足$\beta-\gamma\perp W$.
  只用证$\norm{\beta-\delta}\geqslant \norm{\beta-\gamma}$, 对任意的$\delta\in W$.
  实际上，由勾股定理知
  \begin{align*}
    \norm{\beta-\delta}^2 &=  \norm{(\beta-\gamma)+(\gamma-\delta)}^2\\
    &=  \norm{\beta-\gamma}^2 + \norm{\gamma-\delta}^2\\
    & \geqslant \norm{\beta-\gamma}^2.
  \end{align*}

  \pause
  (3)$\Rightarrow$(1) 
  我们有$V=W\oplus W^{\perp}$. 
  $\beta$可唯一地写成和$\beta=\delta_0+\beta'$, 其中$\delta_0\in W, \beta'\in W^\perp$.  我们要证$\gamma=\delta_0$.
既然$|\beta-\delta|$（其中$\delta\in W$）的最小值在$\delta=\gamma$处取得，我们有
  \[
   \norm{\beta-\delta_0}^2\geqslant \norm{\beta-\gamma}^2,
  \]
  代入$\beta=\delta_0+\beta'$并应用勾股定理知
  \[
    \norm{\beta'}^2\geqslant \norm{\delta_0-\gamma+\beta'}^2= \norm{\delta_0-\gamma}^2+|\beta'|^2.
  \]
  这样$\norm{\delta_0-\gamma}^2=0$, 从而$\delta_0=\gamma$, 得证。
\end{proof}
\end{frame}
\fi
\iffalse
\begin{frame}{行列式的几何解释}
  考虑$n$阶实方阵$A=\begin{pmatrix}
    \alpha_1\\ \vdots \\ \alpha_n
  \end{pmatrix}\in \symbf{R}^{n\times n}$. 
  以原点为起点，$\alpha_1, \cdots, \alpha_n$这些向量为边可以形成一个（可能坍塌的）超平行体。
  如果$n=1$, 这是个线段；如果$n=2$, 这是个平行四边形；如果$n=3$, 这是个平行六面体。
  我们归纳地证明此超平行体的体积就是$A$的行列式的绝对值。
  如果$\alpha_1,\cdots,\alpha_n$线性相关，超平行体坍塌了，此时$A$的行列式也恰好为$0$.
  否则，
\end{frame}
\fi

\begin{frame}{最小二乘法}

  垂线最短这个几何事实可以用来解决一些实际问题，其中的一个应用就是解决最小二乘法问题。先看下面的例子。
 \pause 
 \begin{example}\label{16D}
 已知某种材料在生产过程中的废品率 $y$ 与某种化学成分 $x$ 有关。 下列表中记载了某工厂生产中 $y$ 与相应的 $x$ 的几次数值：
  \begin{center}
     \begin{tabular}{L|LLLLLLL}
        \hline
       y / \% & 1.00 & 0.9 & 0.9 & 0.81 & 0.60 & 0.56 & 0.35 \\
      \hline
     x / \% & 3.6 & 3.7 & 3.8 & 3.9 & 4.0 & 4.1 & 4.2 \\
    \hline
   \end{tabular}
  \end{center}
  我们想找出 $y$ 对 $x$ 的一个近似公式 (即用函数近似拟合数据)。

  \pause
  \begin{figure}[h]
    \centering
\begin{tikzpicture}
  \begin{axis}[scale=.7]
    \addplot[only marks, mark size=1.5pt] coordinates {
(3.6, 1.00)
(3.7, 0.9)
(3.8, 0.9)
(3.9, 0.81)
(4.0, 0.60)
(4.1, 0.56)
(4.2, 0.35)
};
\addplot[thick, domain=3.6:4.2, domain y=0.35:1.1] {-1.05*x+4.81};
\end{axis}
\end{tikzpicture}
  \end{figure}
  \end{example}
\end{frame}

\begin{frame}

 \begin{solution}
  把表中数值画出图来看， 发现它的变化趋势近于一条直线。 
\pause
  因此我们决定选取 $x$ 的一次式 $a x+b$ 来表达。 
\pause
  当然最好能选到适当的 $a, b$ 使得等式
 \[
    \left\{\begin{array}{l}
           3.6 a+b-1.00=0, \\
            3.7 a+b-0.9=0, \\
           3.8 a+b-0.9=0, \\
          3.9 a+b-0.81=0, \\
         4.0 a+b-0.60=0, \\
        4.1 a+b-0.56=0, \\
       4.2 a+b-0.35=0
      \end{array}\right.
     \]
    都成立。 
\pause
    实际上是不可能的。 任何 $a, b$ 代入上面各式都发生些误差。 
\pause
    于是想到找 $a, b$ 使得上面各式的误差的平方和最小，即找 $a, b$ 使
   \[
      \begin{aligned}
   & (3.6 a+b-1.00)^{2}+(3.7 a+b-0.9)^{2}+(3.8 a+b-0.9)^{2}+(3.9 a+b-0.81)^{2} \\
  & +(4.0 a+b-0.60)^{2}+(4.1 a+b-0.56)^{2}+(4.2 a+b-0.35)^{2}
 \end{aligned}
\]
最小。 
\end{solution}


\end{frame}

\begin{frame}
 这里讨论的是误差的平方即二乘方， 故称为\emph{最小二乘法}。 


  ~

  \pause
 现在转向一般的情况。
 线性方程组
 \[
   \left\{\begin{array}{c}
     a_{11} x_{1}+a_{12} x_{2}+\cdots+a_{1 s} x_{s}-b_{1}=0, \\
   a_{21} x_{1}+a_{22} x_{2}+\cdots+a_{2 s} x_{s}-b_{2}=0, \\
 \cdots \cdots \cdots \cdots \cdots \\
 a_{n 1} x_{1}+a_{n 2} x_{2}+\cdots+a_{n s} x_{s}-b_{n}=0
 \end{array}\right.
 \]
 可能无解，即任何一组数 $x_{1}, x_{2}, \cdots, x_s$ 都可能使某个方程
 \[\tag{1}
 \sum_{i=1}^{n}\left(a_{i 1} x_{1}+a_{i 2} x_{2}+\cdots+a_{i s} x_{s}-b_{i}\right)^{2}
 \]
 不等于零。 
\pause
我们设法找 $x_{1}^{0}, x_{2}^{0}, \cdots, x_{s}^{0}$ (实际应用中这些是待定系数) 
使 (1) 最小， 这样的 $x_{1}^{0}, x_{2}^{0}, \cdots, x_{s}^{0}$ 称为方程组的\emph{最小二乘解}。 
\pause
这种问题就叫\emph{ (线性) 最小二乘法问题}。

 \pause
 \begin{sizheng}
最小二乘在实际中应用甚广。习总书记在北大师生座谈会就强调过：学术、知识不能只是在嘴上，要联系实际，做到知行合一、格物致知、学以致用。
 \end{sizheng}
 \end{frame}

 \iffalse
 \begin{frame}
   \begin{sizheng}
    
     高次太高有Runge现象。

     完美拟合不见得是完美的。例如，有时数据关系可能在理论上就是线性的，
     但是由于显示中的复杂环境带来的干扰导致的误差，不能用一个线性函数拟合所有数据。

     Hubble图。 星系逃逸素数与
   \end{sizheng}
 \end{frame}

 \fi
\begin{frame}
  下面我们利用欧氏空间的概念来表达 (线性) 最小二乘法， 并给出最小二乘解所满足的代
 数条件。
\pause
 令
 \[
    A=\begin{pmatrix}
     a_{11} & a_{12} & \cdots & a_{1 s} \\
   a_{21} & a_{22} & \cdots & a_{2 s} \\
 \vdots & \vdots & & \vdots \\
 a_{n 1} & a_{n 2} & \cdots & a_{n s}
 \end{pmatrix}, \quad X=
\begin{pmatrix}
   x_{1} \\
 x_{2} \\
 \vdots \\
 x_{s}
 \end{pmatrix},
 \quad B=\begin{pmatrix}
   b_{1} \\
 b_{2} \\
 \vdots \\
 b_{n}
 \end{pmatrix},\quad 
 Y=\begin{pmatrix}
   \sum_{j=1}^s a_{1j}x_j\\
\sum_{j=1}^s a_{2j}x_j\\
\vdots \\
\sum_{j=1}^s a_{nj}x_j
 \end{pmatrix}=AX.
 \]
 \pause
 用距离的概念， (1) 就是
 \[
   \norm{Y-B}^{2} .
 \]
 \pause
 最小二乘法就是找 $X_0\in\symbf{R}^{(s)}$ 使 $ Y=AX_0$ 与 $ B$ 的距离最短。 
 \pause
 设$A$按列分块为
 \[
   A=\begin{pmatrix}
   \alpha_1 & \cdots & \alpha_s
 \end{pmatrix}.
 \]
 \pause
 令
 \[
   \Span_c A=\Span(\alpha_1, \cdots, \alpha_s)=\{AX\mid X\in \symbf{R}^{(s)}\}
 \]
 为$A$的列空间。
 于是最小二乘法问题可叙述成：

 \textit{找 $ X$ 使 (1) 最小， 就是在$\symbf{R}^{(n)}$的子空间 $\Span_c A$ 中找一向量 $ Y$, 使得 $B$ 到它的距离比到子空间 $\Span_c A$ 中其他向量的距离都短。}
 \end{frame}

 \begin{frame}
   应用引理~\ref{143}， 所要求的向量$Y=AX$
就是$B$在子空间$\Span_c A$中的内射影，这样的$Y$惟一地存在，从而最小二乘解$X$也存在。
\pause
我们还知道
\[
C=B-Y=B-A X
\]
必须垂直于子空间 $\Span_c A = \Span\left( \alpha_{1},  \alpha_{2}, \cdots,  \alpha_{s}\right)$. 
\pause
为此只需而且必须
\[
\pair{ C,  \alpha_{1}}=\pair{ C,  \alpha_{2}}=\cdots=\pair{ C,  \alpha_{s}}=0 .
\]
%回忆矩阵乘法规则， 上述一串等式可以写成矩阵相乘的式子， 即
\pause
或者说，
\[
 \alpha_{1}^{\mathrm{T}}  C=0, \quad  \alpha_{2}^{\mathrm{T}}  C=0, \quad \cdots, \quad  \alpha_{s}^{\mathrm{T}}  C=0 .
\]
\pause
而 $ \alpha_{1}^{\mathrm{T}},  \alpha_{2}^{\mathrm{T}}, \cdots,  \alpha_{s}^{\mathrm{T}}$
按行正好排成矩阵 $ A^{\mathrm{T}}$,上述一串等式合起来就是
\[
 A^{\mathrm{T}}( B- A  X)=\symbf{0},
\]
\pause
亦即
\[
 A^{\mathrm{T}}  A  X= A^{\mathrm{T}}  B .
\]

\pause
这就是最小二乘解所满足的代数方程， 它是一个线性方程组， 
系数矩阵是 $A^{\rT}  A$, 常数项是 $ A^{\mathrm{T}}  B$. 
从我们对垂线最短的讨论就已知最小二乘解存在，因此上面的方程总有解。
%这种线性方程组总是有解的。 
而且，如果$A$列满秩 (指$A$满足其秩等于其列数，或者说，$A$的列向量组线性无关)，
那么$A^{\rT} A$可逆，从而解惟一；
否则，解不惟一，不过可以借助 Moore-Penrose 逆找到长度最小的解，
此解称为\emph{最优最小二乘解}。尽管最小二乘解可能不惟一，前面也提过，
由引理~\ref{143}~知最小二乘解$X$给出的$AX$是惟一确定的，
就是$B$在$\Span_c A$中的内射影。
\end{frame}

\iffalse
\begin{frame}
  \begin{lemma}
    令$A\in \symbf{R}_{m\times n}$. 那么：
    \begin{enumerate}
      \item $\rank(A^{\rT}A)=\rank(A)$. 
      \item 对任意的列向量$B\in \symbf{R}^{(m)}$, 线性方程组$A^{\rT} AX=A^{\rT} B$有解。
        \end{enumerate}
  \end{lemma}
\pause
  \begin{proof}
    \begin{enumerate}
      \item 我们先证明线性方程组 $A^{\rT}AX=0$ 与 $AX=0$同解。 
      诚然，显然$Ax=0$的解是$A^{\rT} AX=0$的解；反过来，
      设 $A^{\rT}AX_0=0$, 那么 
      \[
        0=X_0^{\rT}A^{\rT}AX_0=(AX_0)^{\rT}AX_0=\norm{AX_0}^2, 
      \]
      从而 $AX_0=0$. 
    我们知道$n$元线性方程组$BX=0$的解空间的维数为$n-\rank(B)$.
    这样 $n - \rank ( A^{\rT}A ) = n -  \rank (A)$, 从而$\rank(A^{\rT} A)=\rank(A)$.
    \pause
      \item 
        容易发现$\Span_{c} A^{\rT}A \subset \Span_c A^{\rT}$. 又
        \[
          \dim \Span_c A^{\rT} A = \rank A^{\rT} A = \rank A =\rank A^{\rT} =\dim \Span_c A^{\rT},
        \]
        我们有$\Span_c A^{\rT} A = \Span_c A^{\rT}$.
    这样对任意的 $B\in \symbf{R}^{(m)}$, $A^{\rT}B\in \Span_c A^{\rT}A$, 
    即存在 $X\in \symbf{R}^{(n)}$ 使得 $A^{\rT}AX=A^{\rT}B$. 
    这就证明了 $A^{\rT}AX=A^{\rT}B$ 总有解。
    \end{enumerate}
  \end{proof}
\end{frame}
\fi


\begin{frame}
  \begin{example*}[例~\ref{16D}~ (续)]
 回到前面的例子， 易知
  \[
      A=\begin{pmatrix}
            3.6 & 1 \\
             3.7 & 1 \\
            3.8 & 1 \\
           3.9 & 1 \\
          4.0 & 1 \\
         4.1 & 1 \\
        4.2 & 1
       \end{pmatrix}, \quad  B=\begin{pmatrix}
            1.00 \\
           0.90 \\
          0.90 \\
         0.81 \\
        0.60 \\
       0.56 \\
      0.35
  \end{pmatrix}.
    \]
    \pause
   最小二乘解 $a, b$ 所满足的方程就是
  \[
 A^{\mathrm{T}}  A\begin{pmatrix}
    a \\
     b
    \end{pmatrix}- A^{\mathrm{T}}  B=0,
   \]
   \pause
  即为
 \[
    \left\{\begin{array}{l}
106.75 a+27.3 b-19.675=0 \\
27.3 a+7 b-5.12=0
\end{array}\right.
\]
\pause
解得（取三位有效数字）
\[
a=-1.05,\quad b=4.81.
\]
\end{example*}
\end{frame}


\begin{frame}{小结}
  \begin{enumerate}
    \item 欧氏空间中何为两向量的距离？有何性质？
    \item 何谓垂线最短？
    \item 何谓最小二乘问题？最小二乘解如何获得？
  \end{enumerate}
\end{frame}
